|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
V roce 2001 Stephen Locke vyslovil hypotézu, že pro každou vyváženou množinu F obsahující 2k vadných vrcholů n-rozměrné hyperkrychle Qn, kde n ≥ k +2 a k ≥ 1, je graf Qn −F hamiltonovský. Hypotéza je stále otevřená, byť jsou již známá částečná řešení, někdy i s různými podmínkami na F. V této práci prozkoumáme hamiltonovskost grafu Qn −F, pokud množina vadných vrcholů F tvoří určitý izometrický podgraf v Qn. Pro lichou (resp. sudou) izometrickou cestu P v Qn je graf Qn − V (P) Hamiltonovsky laceabilní pro každé n ≥ 4 (resp. n ≥ 5). Přestože je znám silnější výsledek, metoda důkazu nám umožnila získat následující výsledky. Nechť C je izometrický cyklus v Qn délky dělitelné čtyřmi pro n ≥ 6. Pak je graf Qn − V (C) Hamiltonovsky laceabilní. Buď T izometrický strom v Qn s lichým počtem hran a S izometrický strom v Qm se sudým počtem hran. Pak pro každé n ≥ 4, m ≥ 5 jsou grafy Qn − T a Qm − S Hamiltonovsky laceabilní. Část důkazu je ověřena počítačem. 1
|
|
|
Hamiltonicity of hypercubes without k-snakes and k-coils
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Fink, Jiří (oponent)
Had (cívka) je indukovaná cesta (cyklus) v hyperkrychli. Jsou známí především problé- mem hada v krabici (cívky v krabici) snažící se najít nejdelšího hada (cívku) v hyperkrychli. Jejich zobecnění k-hadi (k-cívky) zachovávají vzdálenosti mezi každými dvěma svými vr- choly, které jsou vzdálené nejvýše k−1 v hyperkrychli. Studujeme je v souvislosti s Lockeho hypotézou. Ta říká, že vyvážené množině F ⊆ V (Qn) vadných vrcholů v hyperkrychli veli- kosti 2m se lze vyhnout Hamiltonovským cyklem pokud n ≥ m+2 a m ≥ 1. My ukazujeme, že pokud S je k-had (k-cívka) pro n ≥ k ≥ 6 (n ≥ k ≥ 7), pak Qn −V (S) je Hamiltonovsky laceabilní. Pro fixované k může být počet vrcholů k-cívky až exponenciální vzhledem k n. Představujeme pojem draka, což je indukovaný strom v hyperkrychli a jeho zobecnění na k-draka, který zachovává vzdálenost mezi každými dvěma svými vrcholy, které jsou vzdá- lené nejvýše k − 1 v hyperkrychli. Dokazujeme specifické lemma které bylo v Bakalářské práci pouze ověřeno počítačem a dokončuje tak důkaz tvrzení o Hamiltonovské laceabilitě hyperkrychlí bez n-draků.
|
|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
V roce 2001 Stephen Locke vyslovil hypotézu, že pro každou vyváženou množinu F obsahující 2k vadných vrcholů n-rozměrné hyperkrychle Qn, kde n ≥ k +2 a k ≥ 1, je graf Qn −F hamiltonovský. Hypotéza je stále otevřená, byť jsou již známá částečná řešení, někdy i s různými podmínkami na F. V této práci prozkoumáme hamiltonovskost grafu Qn −F, pokud množina vadných vrcholů F tvoří určitý izometrický podgraf v Qn. Pro lichou (resp. sudou) izometrickou cestu P v Qn je graf Qn − V (P) Hamiltonovsky laceabilní pro každé n ≥ 4 (resp. n ≥ 5). Přestože je znám silnější výsledek, metoda důkazu nám umožnila získat následující výsledky. Nechť C je izometrický cyklus v Qn délky dělitelné čtyřmi pro n ≥ 6. Pak je graf Qn − V (C) Hamiltonovsky laceabilní. Buď T izometrický strom v Qn s lichým počtem hran a S izometrický strom v Qm se sudým počtem hran. Pak pro každé n ≥ 4, m ≥ 5 jsou grafy Qn − T a Qm − S Hamiltonovsky laceabilní. Část důkazu je ověřena počítačem. 1
|
host ::
RSS.